const int N = 1005;
Dinic<int> gao;
int n, m;
struct Edge {
	int u, v, w;
	Edge() {}
	Edge(int u, int v, int w) : u(u), v(v), w(w) {}
	void read() {scanf("%d%d%d", &u, &v, &w);}
	bool operator < (const Edge& c) const {return w > c.w;}
} e[N * 10], E[N];
int en;

int id[N], S[N], T[N], ans;
void ini() {
	for (int i = 1; i <= n; i++) id[i] = i;
	en = 0, ans = 0;
}
void solve(int l, int r) {
	if (l == r) return;
	gao.ini(n + 1);
	for (int i = 0; i < m; i++) {
		gao.link(e[i].u, e[i].v, e[i].w);
		gao.link(e[i].v, e[i].u, e[i].w);
	}
	int tmp = gao.run(id[l], id[r], n + 1);
	ans += tmp;
	E[en++] = Edge(id[l], id[r], tmp);
	int sn = 0, tn = 0;
	for (int i = l; i <= r; i++) {
		if (gao.level[id[i]] == -1) T[tn++] = id[i];
		else S[sn++] = id[i];
	}
	for (int i = 0; i < sn; i++) id[i + l] = S[i];
	for (int i = 0; i < tn; i++) id[i + l + sn] = T[i];
	solve(l, l + sn - 1);
	solve(l + sn, l + sn + tn - 1);
}
